import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

public class Sort {
    public static int[] randomArr (int maxLen,int maxValue)
    {
        int len = (int)(maxLen*Math.random());
        int[] arr =new int[len];

        for(int i = 0; i<len; i++)
        {
            arr[i] = (int)(maxValue*Math.random());
        }
        return arr;
    }

    public static boolean isOrder(int[] arr)
    {
        int len = arr.length;

        for(int i = 0; i<len-1; i++)
        {
            if(arr[i+1]<arr[i])
            {
                return false;
            }
        }
        return true;
    }

    public static void swap(int[] arr, int index1, int index2)
    {

//        arr[index1] = arr[index1]^arr[index2];
//        arr[index2] = arr[index1]^arr[index2];
//        arr[index1] = arr[index1]^arr[index2];
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static int[] bubbleSort(int[] arr)
    {
        int len = arr.length;
        for(int i = len-2; i>=1; i--)
        {
            for(int j = 0; j<=i;j++)
                if(arr[j]>arr[j+1]){swap(arr,j,j+1);}
        }
        return arr;
    }

    public static int[] insertSort(int[] arr)
    {
        int len = arr.length;
        for(int i = 1; i<len; i++)
        {
            for (int j = i;j>=1;j--)
            {
                if(arr[j]<arr[j-1]){swap(arr,j,j-1);}
            }
        }
        return arr;
    }

    public static int[] selectSort(int[] arr)
    {
        int len = arr.length;
        int min = 999999999;
        int minarg = 0;
        for(int i=0; i<len; i++)
        {
            min = arr[i];
            minarg = i;
            for(int j=i; j<len; j++)
            {
                if(min>arr[j]){min=arr[j];minarg=j;}
            }
            swap(arr,i,minarg);
        }
        return arr;
    }

    public static int[] quickSort(int[] arr)
    {
        int start = 0;
        int end = arr.length-1;
        partition(arr,start,end);
        return arr;
    }

    public static int[] quickSort(int[] arr,int start, int end)
    {
        partition(arr,start,end);
        return arr;
    }

    public static void quickSortNoRecursive(int[] arr){
        class Range{
            public final int l;
            public final int r;

            public Range(int l, int r){
                this.l = l;
                this.r = r;
            }
        } //用于记录范围
        LinkedList<Range> rangeStack = new LinkedList<>();
        Range initRange = new Range(0,arr.length-1);
        rangeStack.push(initRange);//用范围栈的逐步缩小来代替递归过程
        while(!rangeStack.isEmpty()){
            Range temp = rangeStack.pop();
            int p = partitionNoRecersive(arr, temp.l, temp.r);
            if (p - temp.l>1){
                Range left = new Range(temp.l, p-1);
                rangeStack.push(left);
            }
            if (temp.r - p>1){
                Range right = new Range(p+1, temp.r);
                rangeStack.push(right);
            }
        }
    }

    public static void partition(int[] arr,int start,int end)
    {
        if(end-start<0) return;
        int i = start;
        int j = end;
        while(i<j)
        {
            while(i<j && arr[i]<arr[j])
            {
                j--;
            }
            if(i<j)
            {
                swap(arr,i,j);
                i++;
            }

            while(i<j && arr[i]<arr[j])
            {
                i++;
            }
            if(i<j)
            {
                swap(arr,i,j);
                j--;
            }
        }
        partition(arr,start,i-1);
        partition(arr,i+1,end);
    }

    public static int partitionNoRecersive(int[] arr,int start,int end)
    {
        if(end-start<0) return -1;
        int i = start;
        int j = end;
        while(i<j)
        {
            while(i<j && arr[i]<arr[j])
            {
                j--;
            }
            if(i<j)
            {
                swap(arr,i,j);
                i++;
            }

            while(i<j && arr[i]<arr[j])
            {
                i++;
            }
            if(i<j)
            {
                swap(arr,i,j);
                j--;
            }
        }
        return i; //最终枢轴的位置
        //partition(arr,start,i-1);
        //partition(arr,i+1,end);
    }

    public static void mergeSortRecursive(int[] arr){
        mergeSortProcess(arr,0,arr.length);
    }

    public static void mergeSortProcess(int[] arr, int l, int r){
        /*
         * l 第一个数组的开始下标
         * m 第一个数组的结束下标
         * r 第二个数组的结束下标+1
         * */
        if (r-l<2) return; //=1 length为0, =2 length为1
        int m = (r+l-1)/2;
        mergeSortProcess(arr,l,m+1);
        mergeSortProcess(arr,m+1,r);
        merge(arr,l,m,r);
    }

    public static void merge(int[] arr, int l, int m, int r){
        /*
        * l 第一个数组的开始下标
        * m 第一个数组的结束下标
        * r 第二个数组的结束下标+1
        * */
        int pointerL = l;
        int pointerR = m+1;
        int pointerMerge = 0;
        int[] temp = new int[r-l];

        while(pointerMerge<r-l){
            if(pointerL>=m+1){//左边越界
                temp[pointerMerge]=arr[pointerR];
                pointerR++;
            } else if (pointerR>=r) {//右边越界
                temp[pointerMerge]=arr[pointerL];
                pointerL++;
            } else if(arr[pointerL]>arr[pointerR]){ //右边小
                temp[pointerMerge]=arr[pointerR];
                pointerR++;
            } else {// 左边小
                temp[pointerMerge]=arr[pointerL];
                pointerL++;
            }
            pointerMerge++;
        }

        for (int i=0; i<r-l; i++){
            arr[l+i]=temp[i];
        }
    }

    public static void mergeSortNotRecursive(int[] arr){
        int group_size = 1;

        while(group_size<=arr.length){
            int l=0;
            int r=group_size*2;
            int m=(l+r-1)/2;
            while(m+1 < arr.length){//第二组第一个不超出数组范围，也即有第二组
                if (r > arr.length) merge(arr,l,m,arr.length);
                else{merge(arr,l,m,r);}
                l=r;
                r=r+group_size*2;
                m=(l+r-1)/2;
            }

            group_size*=2;
        }
    }

    public static void heapSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            upAdjust(arr,i);
        }

        for(int i=arr.length;i>0;i--){
            downAdjust(arr,0,i);
            swap(arr,0,i-1);
        }
    }

    public static void downAdjust(int[] arr, int idx, int len){
        while(idx*2+1<len){
            int greaterSonIdx = idx*2+1;
            if(idx*2+2<len && arr[idx*2+2]>arr[greaterSonIdx]) greaterSonIdx = idx*2+2;
            if(arr[greaterSonIdx]>arr[idx]){
                swap(arr,idx,greaterSonIdx);
                idx = greaterSonIdx;
            }
            else break;
        }
    }

    public static void upAdjust(int[] arr, int idx){
        int fatherIdx = (idx-1)/2;
        while(idx>0 && arr[fatherIdx]<arr[idx]){
            swap(arr,fatherIdx,idx);
            idx = fatherIdx;
            fatherIdx = (idx-1)/2;
        }
    }

    public static void main(String[] args)
    {
        int[] arr = randomArr(100,100);
        //int[] arr = {2,1,3};
        for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(" ");
        System.out.println(isOrder(arr));
        heapSort(arr);
        for(int i=0;i<arr.length;i++) System.out.print(arr[i]+" ");
        System.out.println(" ");
        System.out.println(isOrder(arr));
    }
}